/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/longest-valid-parentheses
   @Language: C++
   @Datetime: 19-06-04 16:58
   */

class Solution {
public:
	int longestValidParentheses(string s) {
		int res=0;
		vector<int> dp(s.length()+1,0);
		for(int i=1; i<=s.length(); ++i){
			if(s[i]==')'){
				const int pre=i-dp[i-1]-1;
				if(pre==0 && s[pre]=='(')
					dp[i]=dp[i-1]+2;
				else if(pre>0 && s[pre]=='(')
					dp[i]=dp[i-1]+2+dp[pre-1];
			}
			res=max(res,dp[i]);
		}
		return res;
	}
};
